{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #信物传送"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #graph #array #matrix #shortest-path #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #图 #数组 #矩阵 #最短路 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: conveyorBelt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #信物传送"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "欢迎各位勇者来到力扣城，本次试炼主题为「信物传送」。\n",
    "\n",
    "本次试炼场地设有若干传送带，`matrix[i][j]` 表示第 `i` 行 `j` 列的传送带运作方向，`\"^\",\"v\",\"<\",\">\"` 这四种符号分别表示 **上、下、左、右** 四个方向。信物会随传送带的方向移动。勇者**每一次**施法操作，可**临时**变更一处传送带的方向，在物品经过后传送带恢复原方向。\n",
    "![lcp (2).gif](https://pic.leetcode-cn.com/1649835246-vfupSL-lcp%20\\(2\\).gif){:width=300px}\n",
    "\n",
    "通关信物初始位于坐标 `start`处，勇者需要将其移动到坐标 `end` 处，请返回勇者施法操作的最少次数。\n",
    "\n",
    "\n",
    "\n",
    "**注意：**\n",
    "- `start` 和 `end` 的格式均为 `[i,j]`\n",
    "\n",
    "**示例 1:**\n",
    "> 输入：`matrix = [\">>v\",\"v^<\",\"<><\"], start = [0,1], end = [2,0]`\n",
    ">\n",
    "> 输出：`1`\n",
    ">\n",
    "> 解释：\n",
    "> 如上图所示\n",
    "> 当信物移动到 `[1,1]` 时，勇者施法一次将 `[1,1]` 的传送方向 `^` 从变更为 `<`\n",
    "> 从而信物移动到 `[1,0]`，后续到达 `end` 位置\n",
    "> 因此勇者最少需要施法操作 1 次\n",
    "\n",
    "**示例 2:**\n",
    "> 输入：`matrix = [\">>v\",\">>v\",\"^<<\"], start = [0,0], end = [1,1]`\n",
    ">\n",
    "> 输出：`0`\n",
    ">\n",
    "> 解释：勇者无需施法，信物将自动传送至 `end` 位置\n",
    "\n",
    "**示例 3:**\n",
    "> 输入：`matrix = [\">^^>\",\"<^v>\",\"^v^<\"], start = [0,0], end = [1,3]`\n",
    ">\n",
    "> 输出：`3`\n",
    "\n",
    "**提示：**\n",
    "- `matrix` 中仅包含 `'^'、'v'、'<'、'>'`\n",
    "- `0 < matrix.length <= 100`\n",
    "- `0 < matrix[i].length <= 100`\n",
    "- `0 <= start[0],end[0] < matrix.length`\n",
    "- `0 <= start[1],end[1] < matrix[i].length`\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [6UEx57](https://leetcode.cn/problems/6UEx57/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [6UEx57](https://leetcode.cn/problems/6UEx57/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "\n",
    "        visited = [[False]*len(matrix[0]) for _ in range(len(matrix))]\n",
    "        di = {\">\":(0,1),\"<\":(0,-1),\"^\":(-1,0),\"v\":(1,0)}\n",
    "        dui = collections.deque()\n",
    "        x,y = start\n",
    "        while 0<=x<len(matrix) and 0<=y<len(matrix[0]) and not visited[x][y]:\n",
    "            if end == [x,y]:\n",
    "                return 0\n",
    "            visited[x][y] = True\n",
    "            dui.append([x,y])\n",
    "            a,b = di[matrix[x][y]]\n",
    "            x = x+a\n",
    "            y = y+b\n",
    "        ans = 0\n",
    "        while dui:\n",
    "            n = len(dui)\n",
    "            for i in range(n):\n",
    "                x,y = dui.popleft()\n",
    "                for a,b in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                    nextx = x+a\n",
    "                    nexty = y+b\n",
    "                    while 0 <= nextx < len(matrix) and 0 <= nexty < len(matrix[0]) and not visited[nextx][nexty]:\n",
    "                        if end == [nextx, nexty]:\n",
    "                            return ans + 1\n",
    "                        visited[nextx][nexty] = True\n",
    "                        dui.append([nextx, nexty])\n",
    "                        a, b = di[matrix[nextx][nexty]]\n",
    "                        nextx = nextx + a\n",
    "                        nexty = nexty + b\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dist = [[inf for _ in range(n)] for _ in range(m)]\n",
    "        dist[start[0]][start[1]] = 0\n",
    "        q = deque([[start[0], start[1], 0]])\n",
    "        v = {(1, 0): \"v\", (-1, 0): \"^\", (0, 1): \">\", (0, -1): \"<\"}\n",
    "        while q:\n",
    "            s = len(q)\n",
    "            for _ in range(s):\n",
    "                x, y, d = q.popleft()\n",
    "                for l, r in v.keys():\n",
    "                    newX = l + x\n",
    "                    newY = r + y\n",
    "                    if 0 <= newX < m and 0 <= newY < n:\n",
    "                        delta = 0 if v[(l, r)] == matrix[x][y] else 1\n",
    "                        if dist[newX][newY] > delta + d:\n",
    "                            dist[newX][newY] = delta + d\n",
    "                            if delta == 0:\n",
    "                                q.appendleft([newX, newY, d])\n",
    "                            else:\n",
    "                                q.append([newX, newY, delta + d])\n",
    "        return dist[end[0]][end[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        d = {\"^\": 0, \"v\": 2, \"<\": 3, \">\": 1}\n",
    "        i, j = start\n",
    "        q = deque([(i, j)])\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dist = [[inf] * n for _ in range(m)]\n",
    "        dist[i][j] = 0\n",
    "        while 1:\n",
    "            i, j = q.popleft()\n",
    "            if i == end[0] and j == end[1]:\n",
    "                return int(dist[i][j])\n",
    "            for k in range(4):\n",
    "                x, y = i + dirs[k], j + dirs[k + 1]\n",
    "                t = dist[i][j] + int(k != d[matrix[i][j]])\n",
    "                if 0 <= x < m and 0 <= y < n and t < dist[x][y]:\n",
    "                    dist[x][y] = t\n",
    "                    if dist[x][y] == dist[i][j]:\n",
    "                        q.appendleft((x, y))\n",
    "                    else:\n",
    "                        q.append((x, y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "d = {\"^\": (-1, 0),\"v\": (1, 0),\"<\": (0, -1),\">\": (0, 1)}\r\n",
    "class Solution:\r\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\r\n",
    "        m, n = len(matrix), len(matrix[0])\r\n",
    "        q = deque([(0, start[0], start[1])])\r\n",
    "        book = [[1234567890123] * n for _ in range(m)]\r\n",
    "        book[start[0]][start[1]] = 0\r\n",
    "        while q:\r\n",
    "            t, x, y = q.popleft()\r\n",
    "            if [x, y] == end: return t\r\n",
    "            for dr, (dx, dy) in d.items():\r\n",
    "                nx, ny = x + dx, y + dy\r\n",
    "                if not (0 <= nx < m and 0 <= ny < n): continue\r\n",
    "                nt = t + int(dr != matrix[x][y])\r\n",
    "                if dr == matrix[x][y]:\r\n",
    "                    if book[nx][ny] <= t: continue\r\n",
    "                    book[nx][ny] = t\r\n",
    "                    q.appendleft((t, nx, ny))\r\n",
    "                else:\r\n",
    "                    if book[nx][ny] <= t + 1: continue\r\n",
    "                    book[nx][ny] = t + 1\r\n",
    "                    q.append((t + 1, nx, ny))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:      \n",
    "        dir=[[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        mp={'>':[0,1],'<':[0,-1],'v':[1,0],'^':[-1,0]}\n",
    "        l=[start]\n",
    "        cnt=0\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        vi=[[False]*n for i in range(m)]\n",
    "        vi[start[0]][start[1]]=True\n",
    "        while True:\n",
    "            for i in range(len(l)):\n",
    "                cur=l[i]\n",
    "                while True:\n",
    "                    if cur==end:\n",
    "                        return cnt\n",
    "                    d=mp[matrix[cur[0]][cur[1]]]\n",
    "                    cur=[cur[0]+d[0],cur[1]+d[1]]\n",
    "                    if cur[0]>=0 and cur[0]<m and cur[1]>=0 and cur[1]<n and not vi[cur[0]][cur[1]]:\n",
    "                        l.append(cur)\n",
    "                        vi[cur[0]][cur[1]]=True\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "            for i in range(len(l)):\n",
    "                tmp=l.pop(0)\n",
    "                for d in dir:\n",
    "                    cur=[tmp[0]+d[0],tmp[1]+d[1]]\n",
    "                    if cur[0]>=0 and cur[0]<m and cur[1]>=0 and cur[1]<n and not vi[cur[0]][cur[1]]:\n",
    "                        l.append(cur)\n",
    "                        vi[cur[0]][cur[1]]=True\n",
    "            cnt+=1\n",
    "        return 0\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        # res = inf\n",
    "        # directions = {\n",
    "        #     \"^\": (-1, 0),\n",
    "        #     \"v\": (1, 0),\n",
    "        #     \"<\": (0, -1),\n",
    "        #     \">\": (0, 1),\n",
    "        # }\n",
    "        # queue = [[0, start[0],start[1]]]\n",
    "        # seen = set()\n",
    "        # while queue:\n",
    "        #     count, x, y = heappop(queue)\n",
    "        #     if [x, y] == end:\n",
    "        #         return count \n",
    "        #     seen.add((x, y))\n",
    "        #     for ch, d in directions.items():\n",
    "        #         new_x, new_y = x+d[0], y+d[1]\n",
    "        #         if 0 <= new_x < len(matrix) and 0 <= new_y < len(matrix[0]) \\\n",
    "        #             and (new_x, new_y) not in seen:\n",
    "        #             if ch == matrix[x][y]:\n",
    "        #                 heappush(queue, [count, new_x, new_y])\n",
    "        #             else:\n",
    "        #                 heappush(queue, [count+1, new_x, new_y])\n",
    "        # return 0\n",
    "\n",
    "        # ------------------------------\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        dist = [[inf] * n for _ in range(m)]\n",
    "        dist[start[0]][start[1]] = 0\n",
    "        q = collections.deque([[start[0], start[1], 0]])\n",
    "        v = {(1, 0): \"v\", (-1, 0): \"^\", (0, 1): \">\", (0, -1): \"<\"}\n",
    "        while q:\n",
    "            s = len(q)\n",
    "            for _ in range(s):\n",
    "                x, y, d = q.popleft()\n",
    "                for l, r in v.keys():\n",
    "                    newX = l + x\n",
    "                    newY = r + y\n",
    "                    if 0 <= newX < m and 0 <= newY < n:\n",
    "                        o = 0 if v[(l, r)] == matrix[x][y] else 1\n",
    "                        if dist[newX][newY] > o + d:\n",
    "                            dist[newX][newY] = o + d\n",
    "                            if o == 0:\n",
    "                                q.appendleft([newX, newY, d])\n",
    "                            else:\n",
    "                                q.append([newX, newY, o + d])\n",
    "        return dist[end[0]][end[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        r,c = len(matrix),len(matrix[0])\n",
    "        dist = [float('inf')]*(r*c)\n",
    "        sx,sy = start[0],start[1]\n",
    "        dist[sx*c+sy] = 0\n",
    "        dx = [-1,1,0,0]\n",
    "        dy = [0,0,-1,1]\n",
    "        letter_to_num = {'^':0,'v':1,'<':2,'>':3}\n",
    "        ex,ey=end[0],end[1]\n",
    "        # visited = set()\n",
    "        queue = deque([(sx,sy)])\n",
    "        while queue:\n",
    "            x,y=queue.popleft()\n",
    "            cur_pos = x*c +y\n",
    "            for i in range(4):\n",
    "                nx,ny = x+dx[i], y+dy[i]\n",
    "                n_pos = nx*c + ny\n",
    "                new_dist = dist[cur_pos] + (0 if letter_to_num[matrix[x][y]]==i else 1)\n",
    "                if 0<=nx<r and 0<=ny<c and new_dist<dist[n_pos]:\n",
    "                    dist[n_pos] = new_dist\n",
    "                    if letter_to_num[matrix[x][y]] == i:\n",
    "                        queue.appendleft((nx,ny))\n",
    "                    else:\n",
    "                        queue.append((nx, ny))\n",
    "            pass\n",
    "        \n",
    "        return dist[ex*c+ey]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        r,c = len(matrix),len(matrix[0])\n",
    "        dist = [float('inf')] * (r*c)\n",
    "        sx,sy = start[0],start[1]\n",
    "        dist[sx*c+sy] = 0\n",
    "        dx = [-1,1,0,0]\n",
    "        dy = [0,0,-1,1]\n",
    "        letter_to_num = {'^':0, 'v':1, '<':2, '>':3}\n",
    "        queue = [(0,sx,sy)]\n",
    "        while queue:\n",
    "            dis,x,y = heapq.heappop(queue)\n",
    "            if dist[x*c+y]<dis:\n",
    "                continue\n",
    "            for i in range(4):\n",
    "                nx,ny = x+dx[i],y+dy[i]\n",
    "                n_pos = nx*c + ny\n",
    "                new_dist = dis + (0 if letter_to_num[matrix[x][y]]==i else 1)\n",
    "                if 0<=nx<r and 0<=ny<c and new_dist<dist[n_pos]:\n",
    "                    dist[n_pos] = new_dist\n",
    "                    heapq.heappush(queue, (dist[n_pos], nx, ny))\n",
    "        ex,ey = end[0],end[1]\n",
    "        return dist[ex*c + ey]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        # BFS：因为要直接搜索，所以visited表示从起点到该点的最短距离，初始为inf,表示不可达，然后进行全局搜索，直到全部走一遍？似乎不行，因为你不确定什么时候收敛，当一个点的距离不减少时，就不用加入队列了\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        visited = [[math.inf]*n for _ in range(m)]\n",
    "        visited[start[0]][start[1]] = 0\n",
    "        q = deque()\n",
    "        q.appendleft((start[0], start[1], 0))\n",
    "        result = abs(start[0]-end[0]) + abs(start[1]-end[1])\n",
    "        code_map = {'^': [-1, 0], 'v': [1, 0], '<': [0, -1], '>': [0, 1]}\n",
    "        while q:\n",
    "            x, y, cost = q.popleft()\n",
    "            if [x, y] == end:\n",
    "                result = min(result, cost)\n",
    "                # return result\n",
    "            for dx, dy in code_map.values():\n",
    "                tmp_x, tmp_y = x + dx, y + dy\n",
    "                if 0 <= tmp_x < m and 0 <= tmp_y < n:\n",
    "                    if code_map[matrix[x][y]] == [dx, dy]:\n",
    "                        tmp_cost = cost\n",
    "                    else:\n",
    "                        tmp_cost = cost + 1\n",
    "                    if tmp_cost < visited[tmp_x][tmp_y] and tmp_cost <= result:  # 这里需要剪枝，超出时间限制\n",
    "                        visited[tmp_x][tmp_y] = tmp_cost\n",
    "                        q.appendleft((tmp_x, tmp_y, tmp_cost))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        maxc = abs(start[0]-end[0])+abs(start[1]-end[1])\n",
    "        q = [] # q=deque()\n",
    "        heappush(q,(0, start[0],start[1]))  # q.appendleft((start[0],start[1],0))\n",
    "        vis=set()\n",
    "        \n",
    "        d={'^':(-1,0),'v':(1,0),'<':(0,-1),'>':(0,1)}\n",
    "        res=maxc\n",
    "        while q:\n",
    "            c, x,y = heappop(q)  # q.pop()\n",
    "            if (x,y) in vis:\n",
    "                continue\n",
    "            vis.add((x,y))\n",
    "            if [x,y]==end:\n",
    "                # print((x,y,c))\n",
    "                # res=min(res,c)\n",
    "                return c\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if m>xx>=0<=yy<n:\n",
    "                    if d[matrix[x][y]]==(dx,dy):\n",
    "                        cc=c\n",
    "                    else:\n",
    "                        cc=c+1\n",
    "                    if (xx,yy) not in vis and cc<=maxc:\n",
    "                        heappush(q, (cc,xx,yy))  # q.appendleft((xx,yy,cc))\n",
    "                        # vis.add((xx,yy,cc))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        # 100*100\n",
    "        # 从start花费cost到达[i,j],记为(i,j,c) , 最大 maxc\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        maxc = abs(start[0]-end[0])+abs(start[1]-end[1])\n",
    "        q = [] # q=deque()\n",
    "        heappush(q,(0, start[0],start[1]))  # q.appendleft((start[0],start[1],0))\n",
    "        vis=set()\n",
    "        \n",
    "        d={'^':(-1,0),'v':(1,0),'<':(0,-1),'>':(0,1)}\n",
    "        res=maxc\n",
    "        while q:\n",
    "            c, x,y = heappop(q)  # q.pop()\n",
    "            if (x,y) in vis:\n",
    "                continue\n",
    "            vis.add((x,y))\n",
    "            if [x,y]==end:\n",
    "                # print((x,y,c))\n",
    "                # res=min(res,c)\n",
    "                return c\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if m>xx>=0<=yy<n:\n",
    "                    if d[matrix[x][y]]==(dx,dy):\n",
    "                        cc=c\n",
    "                    else:\n",
    "                        cc=c+1\n",
    "                    if (xx,yy) not in vis and cc<=maxc:\n",
    "                        heappush(q, (cc,xx,yy))  # q.appendleft((xx,yy,cc))\n",
    "                        # vis.add((xx,yy,cc))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "d = {\"^\": (-1, 0),\"v\": (1, 0),\"<\": (0, -1),\">\": (0, 1)}\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        q = deque([(0, start[0], start[1])])\n",
    "        book = [[1234567890123] * n for _ in range(m)]\n",
    "        book[start[0]][start[1]] = 0\n",
    "        while q:\n",
    "            t, x, y = q.popleft()\n",
    "            if [x, y] == end: return t\n",
    "            for dr, (dx, dy) in d.items():\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if not (0 <= nx < m and 0 <= ny < n): continue\n",
    "                nt = t + int(dr != matrix[x][y])\n",
    "                if dr == matrix[x][y]:\n",
    "                    if book[nx][ny] <= t: continue\n",
    "                    book[nx][ny] = t\n",
    "                    q.appendleft((t, nx, ny))\n",
    "                else:\n",
    "                    if book[nx][ny] <= t + 1: continue\n",
    "                    book[nx][ny] = t + 1\n",
    "                    q.append((t + 1, nx, ny))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        dirlist = ['^','v','<','>']\n",
    "        dirvec = [[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        vis = [ [False]*m for _ in range(n) ]\n",
    "        distane = [ [math.inf] * m for _ in range(n) ]\n",
    "        que = [start]\n",
    "        distane[start[0]][start[1]] = 0\n",
    "        while True:\n",
    "            now = que.pop(0)\n",
    "            nowX , nowY = now[0] , now[1]\n",
    "            if now == end:\n",
    "                return distane[nowX][nowY]\n",
    "            if vis[nowX][nowY] == True:\n",
    "                continue\n",
    "            else:\n",
    "                vis[nowX][nowY] = True\n",
    "            for i in range(4):\n",
    "                nextX , nextY = nowX+dirvec[i][0] , nowY+dirvec[i][1]\n",
    "                if nextX<0 or nextX>=n or nextY<0 or nextY>=m:\n",
    "                    continue\n",
    "                if matrix[nowX][nowY] == dirlist[i]:\n",
    "                    que.insert(0,[nextX,nextY])\n",
    "                    distane[nextX][nextY] = min(distane[nextX][nextY],distane[nowX][nowY])\n",
    "                else:\n",
    "                    que.append([nextX,nextY])\n",
    "                    distane[nextX][nextY] = min(distane[nextX][nextY], distane[nowX][nowY]+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        steps1 = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        steps2 = {'^':(-1, 0), 'v':(1, 0), '<':(0, -1), '>':(0, 1)}\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dist = [[-1] * n for _ in range(m)]\n",
    "        q = [(0, start[0], start[1])]\n",
    "        while len(q) > 0:\n",
    "            d, i, j = heapq.heappop(q)\n",
    "            if i == end[0] and j == end[1]: return d\n",
    "            if dist[i][j] > -1: continue\n",
    "            dist[i][j] = d\n",
    "            for ii, jj in steps1:\n",
    "                if (i + ii) >= 0 and (i + ii) < m and (j + jj) >= 0 and (j + jj) < n:\n",
    "                    heapq.heappush(q, (d + 1, i + ii, j + jj))\n",
    "            ii, jj = steps2[matrix[i][j]][0], steps2[matrix[i][j]][1]\n",
    "            if (i + ii) >= 0 and (i + ii) < m and (j + jj) >= 0 and (j + jj) < n:\n",
    "                    heapq.heappush(q, (d, i + ii, j + jj))\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        options = {'>':lambda x,y :(x,y+1),'<':lambda x,y:(x,y-1),'^':lambda x,y:(x-1,y),'v':lambda x,y:(x+1,y)}\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        queue = []\n",
    "        x,y = start\n",
    "        queue.append([0,x,y])\n",
    "        visited = set()\n",
    "        while queue:\n",
    "            count,x,y = heappop(queue)\n",
    "            if [x,y] == end:\n",
    "                return count\n",
    "            if (x,y) in visited:\n",
    "                continue\n",
    "            visited.add((x,y))\n",
    "            newX,newY = options[matrix[x][y]](x,y)\n",
    "            if 0<=newX<m and 0<=newY<n and (newX,newY) not in visited:\n",
    "                heappush(queue,[count,newX,newY])\n",
    "            for i,j in [[x,y+1],[x,y-1],[x+1,y],[x-1,y]]:\n",
    "                if not(0<=i<m and 0<=j<n) or (i,j) in visited or [i,j] == [newX,newY]:\n",
    "                    continue\n",
    "                heappush(queue,[count+1,i,j])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = {\"^\":(-1, 0), \"v\":(1, 0), \"<\":(0, -1), \">\":(0, 1)}\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        # 基本参数\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        i, j = start\n",
    "        # 准备工作，一个地图，一个集合，一个堆\n",
    "        dist = [[inf] * n for _ in range(m)]\n",
    "        dist[i][j] = 0\n",
    "        seen = set()\n",
    "        h = [(0, i, j)]\n",
    "        # 开始走起来\n",
    "        while h:\n",
    "            d, i, j = heappop(h)\n",
    "            if [i, j] == end: return d\n",
    "            if (i, j) in seen: continue\n",
    "            seen.add((i, j))\n",
    "            for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):\n",
    "                if m > x >= 0 <= y < n:\n",
    "                    nd = d + int((x - i, y - j) != DIRS[matrix[i][j]])\n",
    "                    if nd < dist[x][y]:\n",
    "                        dist[x][y] = nd\n",
    "                        heappush(h, (nd, x, y))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        r, c = len(matrix), len(matrix[0])\n",
    "\n",
    "        queue = collections.deque([(start[0], start[1], 0)])\n",
    "        seen = set()\n",
    "\n",
    "        mp = {\n",
    "            '^':(-1,0),\n",
    "            'v':(1, 0),\n",
    "            '<':(0, -1),\n",
    "            '>':(0, 1)\n",
    "        }\n",
    "\n",
    "        while queue:\n",
    "            i, j, step = queue.popleft()\n",
    "            if i == end[0] and j == end[1]:\n",
    "                return step\n",
    "\n",
    "            if (i,j) in seen:\n",
    "                continue\n",
    "            \n",
    "            seen.add((i, j))\n",
    "\n",
    "            for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                newi, newj = i + di, j + dj\n",
    "                if 0 <= newi < r and 0 <= newj < c:\n",
    "                    if mp[matrix[i][j]] == (di, dj):\n",
    "                        queue.appendleft((newi, newj, step))\n",
    "                    else:\n",
    "                        queue.append((newi, newj, step + 1))\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        m,n = len(matrix), len(matrix[0])\n",
    "        temp = {(0,1):'>',(0,-1):'<',(1,0):'v',(-1,0):'^'}\n",
    "        max_ = abs(start[0]-end[0])+abs(start[1]-end[1])\n",
    "        dp = [[max_]*n for i in range(m)]\n",
    "        dp[start[0]][start[1]] = 0\n",
    "        def helper(a, b, cur):\n",
    "            if a==end[0] and b==end[1]:\n",
    "                return\n",
    "            for da,db in temp.keys():\n",
    "                k = a+da\n",
    "                t = b+db\n",
    "                if 0<=k<m and 0 <=t<n and dp[k][t]>cur:\n",
    "                    xxx = 0\n",
    "                    if matrix[a][b]!=temp[(da,db)]:\n",
    "                        xxx = 1\n",
    "                    data = dp[k][t]\n",
    "                    dp[k][t] = min(dp[k][t], cur+xxx)\n",
    "                    if dp[k][t] < data:\n",
    "                        helper(k,t, dp[k][t])\n",
    "        helper(start[0],start[1], 0)\n",
    "        return dp[end[0]][end[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        m,n = len(matrix), len(matrix[0])\n",
    "        temp = {(0,1):'>',(0,-1):'<',(1,0):'v',(-1,0):'^'}\n",
    "        max_ = abs(start[0]-end[0])+abs(start[1]-end[1])\n",
    "        dp = [[max_]*n for i in range(m)]\n",
    "        dp[start[0]][start[1]] = 0\n",
    "        # @functools.lru_cache(None)\n",
    "        def helper(a, b, cur):\n",
    "            if a==end[0] and b==end[1]:\n",
    "                return\n",
    "            for da,db in temp.keys():\n",
    "                k = a+da\n",
    "                t = b+db\n",
    "                if 0<=k<m and 0 <=t<n and dp[k][t]>cur:\n",
    "                    xxx = 0\n",
    "                    if matrix[a][b]!=temp[(da,db)]:\n",
    "                        xxx = 1\n",
    "                    data = cur+xxx\n",
    "                    if data < dp[k][t]:\n",
    "                        dp[k][t] = data\n",
    "                        helper(k,t, dp[k][t])\n",
    "        helper(start[0],start[1], 0)\n",
    "        return dp[end[0]][end[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        m,n = len(matrix), len(matrix[0])\n",
    "        temp = {(0,1):'>',(0,-1):'<',(1,0):'v',(-1,0):'^'}\n",
    "        max_ = abs(start[0]-end[0])+abs(start[1]-end[1])\n",
    "        dp = [[max_]*n for i in range(m)]\n",
    "        dp[start[0]][start[1]] = 0\n",
    "        def helper(a, b, cur):\n",
    "            if a==end[0] and b==end[1]:\n",
    "                return\n",
    "            for da,db in temp.keys():\n",
    "                k = a+da\n",
    "                t = b+db\n",
    "                if 0<=k<m and 0 <=t<n and dp[k][t]>cur:\n",
    "                    xxx = 0\n",
    "                    if matrix[a][b]!=temp[(da,db)]:\n",
    "                        xxx = 1\n",
    "                    dp[k][t] = min(dp[k][t], cur+xxx)\n",
    "                    helper(k,t, dp[k][t])\n",
    "        helper(start[0],start[1], 0)\n",
    "        return dp[end[0]][end[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        m,n = len(matrix), len(matrix[0])\n",
    "        temp = {(0,1):'>',(0,-1):'<',(1,0):'v',(-1,0):'^'}\n",
    "        max_ = abs(start[0]-end[0])+abs(start[1]-end[1])\n",
    "        dp = [[max_]*n for i in range(m)]\n",
    "        dp[start[0]][start[1]] = 0\n",
    "        # @functools.lru_cache(None)\n",
    "        def helper(a, b, cur):\n",
    "            if a==end[0] and b==end[1]:\n",
    "                return\n",
    "            for da,db in temp.keys():\n",
    "                k = a+da\n",
    "                t = b+db\n",
    "                if 0<=k<m and 0 <=t<n and dp[k][t]>cur:\n",
    "                    xxx = 0\n",
    "                    if matrix[a][b]!=temp[(da,db)]:\n",
    "                        xxx = 1\n",
    "                    data = dp[k][t]\n",
    "                    dp[k][t] = min(dp[k][t], cur+xxx)\n",
    "                    if dp[k][t] < data:\n",
    "                        helper(k,t, dp[k][t])\n",
    "        helper(start[0],start[1], 0)\n",
    "        return dp[end[0]][end[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        #迪杰斯特拉，用操作次数作为时间\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        direct = [(1, 0), (-1, 0), (0, -1), (0, 1)]\n",
    "        import heapq\n",
    "        vst = set()\n",
    "        q = []\n",
    "        heapq.heappush(q, (0, (start[0], start[1])))\n",
    "        end = (end[0], end[1])\n",
    "\n",
    "        while q:\n",
    "            opera, u = heapq.heappop(q)\n",
    "            print(u)\n",
    "            if u[0] == end[0] and u[1] == end[1]:\n",
    "                return opera\n",
    "            if u in vst:\n",
    "                continue\n",
    "            vst.add((u[0], u[1]))\n",
    "            for dx, dy in direct:\n",
    "                nx = u[0] + dx\n",
    "                ny = u[1] + dy\n",
    "                if 0<= nx < m and 0<= ny < n:\n",
    "                    if matrix[u[0]][u[1]] == \"^\":\n",
    "                        if dx == -1 and dy == 0:\n",
    "                            heapq.heappush(q, (opera, (nx, ny)))\n",
    "                        else:\n",
    "                            heapq.heappush(q, (opera+1, (nx, ny)))\n",
    "\n",
    "                    if matrix[u[0]][u[1]] == \"v\":\n",
    "                        if dx == 1 and dy == 0:\n",
    "                            heapq.heappush(q, (opera, (nx, ny)))\n",
    "                        else:\n",
    "                            heapq.heappush(q, (opera+1, (nx, ny)))\n",
    "                    \n",
    "                    if matrix[u[0]][u[1]] == \"<\":\n",
    "                        if dx == 0 and dy == -1:\n",
    "                            heapq.heappush(q, (opera, (nx, ny)))\n",
    "                        else:\n",
    "                            heapq.heappush(q, (opera+1, (nx, ny)))\n",
    "\n",
    "                    if matrix[u[0]][u[1]] == \">\":\n",
    "                        if dx == 0 and dy == 1:\n",
    "                            heapq.heappush(q, (opera, (nx, ny)))\n",
    "                        else:\n",
    "                            heapq.heappush(q, (opera+1, (nx, ny)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "LEFT, RIGHT, UP, DOWN = (0, -1), (0, 1), (-1, 0), (1, 0)\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        que = Queue()\n",
    "        que.put(start)\n",
    "        dic = collections.defaultdict()\n",
    "        dic[(start[0], start[1])] = 0\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        ret = n * m\n",
    "        while not que.empty():\n",
    "            x, y = que.get()\n",
    "            if (x, y) == (end[0], end[1]):\n",
    "                ret = min(ret, dic[(end[0], end[1])])\n",
    "                continue\n",
    "            for dx, dy in (UP, DOWN, LEFT, RIGHT):\n",
    "                tx, ty = x + dx, y + dy\n",
    "                if 0 <= tx < n and 0 <= ty < m:\n",
    "                    tdir = dic[(x, y)] + 1\n",
    "                    if (dx, dy) == UP and matrix[x][y] == \"^\": tdir -= 1\n",
    "                    if (dx, dy) == DOWN and matrix[x][y] == \"v\": tdir -= 1\n",
    "                    if (dx, dy) == LEFT and matrix[x][y] == \"<\": tdir -= 1\n",
    "                    if (dx, dy) == RIGHT and matrix[x][y] == \">\": tdir -= 1\n",
    "                    if dic.get((tx, ty), n * m) > tdir:\n",
    "                        dic[(tx, ty)] = tdir\n",
    "                        que.put([tx, ty])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        r,c = len(matrix),len(matrix[0])\n",
    "        dist = [float('inf')]*(r*c)\n",
    "        sx,sy = start[0],start[1]\n",
    "        dist[sx*c+sy] = 0\n",
    "        dx = [-1,1,0,0]\n",
    "        dy = [0,0,-1,1]\n",
    "        letter_to_num = {'^':0,'v':1,'<':2,'>':3}\n",
    "        ex,ey=end[0],end[1]\n",
    "        visited = set()\n",
    "        queue = deque([(sx,sy)])\n",
    "        while queue:\n",
    "            x,y=queue.popleft()\n",
    "            if (x,y) in visited:\n",
    "                continue\n",
    "            visited.add((x,y))\n",
    "            cur_pos = x*c +y\n",
    "            for i in range(4):\n",
    "                nx,ny = x+dx[i], y+dy[i]\n",
    "                n_pos = nx*c + ny\n",
    "                new_dist = dist[cur_pos] + (0 if letter_to_num[matrix[x][y]]==i else 1)\n",
    "                if 0<=nx<r and 0<=ny<c and new_dist<dist[n_pos]:\n",
    "                    dist[n_pos] = new_dist\n",
    "                    if letter_to_num[matrix[x][y]] == i:\n",
    "                        queue.appendleft((nx,ny))\n",
    "                    else:\n",
    "                        queue.append((nx, ny))\n",
    "            pass\n",
    "        \n",
    "        return dist[ex*c+ey]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        m = {\n",
    "            \"v\": 0,\n",
    "            \"^\": 1,\n",
    "            \">\": 2,\n",
    "            \"<\": 3,\n",
    "        }\n",
    "        vis = {(start[0], start[1]): 0}\n",
    "        best = set()\n",
    "        deq = deque([(0, start[0], start[1])])\n",
    "\n",
    "        while deq:\n",
    "            wei, i, j = deq.popleft()\n",
    "            if (i, j) in best:\n",
    "                continue\n",
    "            best.add((i, j))\n",
    "            for p, pos in enumerate(((i+1, j), (i-1, j), (i, j+1), (i, j-1))):\n",
    "                x, y = pos\n",
    "                if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]):\n",
    "                    w = wei + 1\n",
    "                    if p == m[matrix[i][j]]:\n",
    "                        w -= 1\n",
    "                    if (not (x, y) in vis) or ((x, y) not in best and w < vis[(x, y)]):\n",
    "                        vis[(x, y)] = w\n",
    "                        if w == wei:\n",
    "                            deq.appendleft((w, x, y))\n",
    "                        else:\n",
    "                            deq.append((w, x, y))\n",
    "        return vis[(end[0], end[1])]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        visited = set()\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        que = []\n",
    "        \n",
    "        def dfs(cur):\n",
    "            if cur in visited:\n",
    "                return\n",
    "            else:\n",
    "                visited.add(cur)\n",
    "                nxt = None\n",
    "                match matrix[cur[0]][cur[1]]:\n",
    "                    case \"^\":\n",
    "                        nxt = (cur[0]-1, cur[1])\n",
    "                    case \"v\":\n",
    "                        nxt = (cur[0]+1, cur[1])\n",
    "                    case \"<\":\n",
    "                        nxt = (cur[0], cur[1]-1)\n",
    "                    case \">\":\n",
    "                        nxt = (cur[0], cur[1]+1)\n",
    "                for nx, ny in [[cur[0]-1, cur[1]], [cur[0]+1, cur[1]], [cur[0], cur[1]-1], [cur[0], cur[1]+1]]:\n",
    "                    if 0 <= nx < m and 0 <= ny < n:\n",
    "                        if (nx, ny) == nxt:\n",
    "                            dfs(nxt)\n",
    "                        else:\n",
    "                            que.append((nx, ny))\n",
    "            \n",
    "        temp = [tuple(start)]\n",
    "        end = tuple(end)\n",
    "        while temp:\n",
    "            for _ in range(len(temp)):\n",
    "                dfs(temp.pop())\n",
    "            if end in visited:\n",
    "                return ans\n",
    "            ans += 1\n",
    "            temp = que[:]\n",
    "            que = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        res = inf\n",
    "        directions = {\n",
    "            \"^\": (-1, 0),\n",
    "            \"v\": (1, 0),\n",
    "            \"<\": (0, -1),\n",
    "            \">\": (0, 1),\n",
    "        }\n",
    "        queue = [[0, start[0],start[1]]]\n",
    "        seen = set()\n",
    "        while queue:\n",
    "            count, x, y = heappop(queue)\n",
    "            if [x, y] == end:\n",
    "                return count \n",
    "            seen.add((x, y))\n",
    "            for ch, d in directions.items():\n",
    "                new_x, new_y = x+d[0], y+d[1]\n",
    "                if 0 <= new_x < len(matrix) and 0 <= new_y < len(matrix[0]) \\\n",
    "                    and (new_x, new_y) not in seen:\n",
    "                    if ch == matrix[x][y]:\n",
    "                        heappush(queue, [count, new_x, new_y])\n",
    "                    else:\n",
    "                        heappush(queue, [count+1, new_x, new_y])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "\n",
    "        row=len(matrix)\n",
    "        line=len(matrix[0])\n",
    "        def to_position(current_postion, temp_direction):\n",
    "            temp_row=current_postion[0]\n",
    "            temp_line=current_postion[1]\n",
    "            direction=dict()\n",
    "\n",
    "            direction[\"^\"]=[-1, 0]\n",
    "            direction[\"v\"]=[1, 0]\n",
    "            direction[\"<\"]=[0, -1]\n",
    "            direction[\">\"]=[0, 1]\n",
    "\n",
    "            # current_direction=matrix[temp_row][temp_line]\n",
    "            current_direction=temp_direction\n",
    "\n",
    "            temp_row+=direction[current_direction][0]\n",
    "            temp_line+=direction[current_direction][1]\n",
    "            if temp_row<0 or temp_row>=len(matrix) or temp_line<0 or temp_line>=len(matrix[0]):\n",
    "                return \"\"\n",
    "            return str(temp_row)+\"_\"+str(temp_line)\n",
    "\n",
    "        queue_list=[start]\n",
    "\n",
    "        flag=0\n",
    "        distance=0\n",
    "        path=dict()\n",
    "        path[str(start[0])+\"_\"+str(start[1])]=0\n",
    "        while flag<len(queue_list):\n",
    "            for direction in [\"^\",\"v\",\"<\",\">\"]:\n",
    "                if direction!=matrix[queue_list[flag][0]][queue_list[flag][1]]:\n",
    "                    # 需要变换方向\n",
    "                    target_postion=to_position(queue_list[flag], direction)\n",
    "                    # print(queue_list[flag], target_postion)\n",
    "                    if len(target_postion):\n",
    "                        if target_postion not in path:\n",
    "                            path[target_postion]=path[\"{}_{}\".format(queue_list[flag][0], queue_list[flag][1])]+1\n",
    "                            temp_postion=target_postion.split(\"_\")\n",
    "                            queue_list.append([int(x) for x in temp_postion])\n",
    "                        else:\n",
    "                            if path[\"{}_{}\".format(queue_list[flag][0], queue_list[flag][1])]+1<path[target_postion]:\n",
    "                                path[target_postion]=path[\"{}_{}\".format(queue_list[flag][0], queue_list[flag][1])]+1\n",
    "                                temp_postion=target_postion.split(\"_\")\n",
    "                                queue_list.append([int(x) for x in temp_postion])\n",
    "                else:\n",
    "                    target_postion=to_position(queue_list[flag], direction)\n",
    "                    # print(queue_list[flag], target_postion)\n",
    "                    if len(target_postion):\n",
    "                        if target_postion not in path:\n",
    "                            path[target_postion]=path[\"{}_{}\".format(queue_list[flag][0], queue_list[flag][1])]+0\n",
    "                            temp_postion=target_postion.split(\"_\")\n",
    "                            queue_list.append([int(x) for x in temp_postion])\n",
    "                        else:\n",
    "                            if path[\"{}_{}\".format(queue_list[flag][0], queue_list[flag][1])]+0<path[target_postion]:\n",
    "                                path[target_postion]=path[\"{}_{}\".format(queue_list[flag][0], queue_list[flag][1])]+0\n",
    "                                temp_postion=target_postion.split(\"_\")\n",
    "                                queue_list.append([int(x) for x in temp_postion])\n",
    "            # print(path)\n",
    "            flag+=1\n",
    "        return path[\"{}_{}\".format(end[0], end[1])]\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Dijkstra:\n",
    "    def __init__(self, edges=[], undirected=True):\n",
    "        self.g = defaultdict(list)\n",
    "        self.undirected = undirected\n",
    "        for x, y, w in edges: self.add_edge(x, y, w)\n",
    "    def get_min_dist(self, src=0):\n",
    "        dist = defaultdict(lambda:inf)\n",
    "        dist[src] = 0\n",
    "        sl = [(dist[src], src)]\n",
    "        while sl:\n",
    "            d, x = heappop(sl)\n",
    "            for y, cost in self.g[x]:\n",
    "                if dist[x] + cost < dist[y]:\n",
    "                    dist[y] = dist[x] + cost\n",
    "                    heappush(sl, (dist[y], y))\n",
    "        return dist\n",
    "    def add_edge(self, x, y, w):\n",
    "        self.g[x].append((y, w))\n",
    "        if self.undirected: self.g[y].append((x, w))\n",
    "        \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        dct = dict(zip([(-1, 0), (1, 0), (0, -1), (0, 1)], [\"^\",\"v\",\"<\",\">\"]))\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        dijkstra = Dijkstra(edges=[], undirected=False)\n",
    "        # dijkstra.add_edge(x, y, w)\n",
    "\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                for dx, dy in (0, 1), (1, 0), (-1, 0), (0, -1):\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n:\n",
    "                        dijkstra.add_edge((x, y), (nx, ny), int(dct[(dx, dy)] != matrix[x][y]))\n",
    "        src, dst = tuple(start), tuple(end)\n",
    "        min_dist = dijkstra.get_min_dist(src=src)[dst]  \n",
    "        return min_dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt_hq(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        # 100*100\n",
    "        # 从start花费cost到达[i,j],记为(i,j,c) , 最大 maxc\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        maxc = abs(start[0]-end[0])+abs(start[1]-end[1])\n",
    "        q = [] # q=deque()\n",
    "        heappush(q,(0, start[0],start[1]))  # q.appendleft((start[0],start[1],0))\n",
    "        vis=set()\n",
    "        \n",
    "        d={'^':(-1,0),'v':(1,0),'<':(0,-1),'>':(0,1)}\n",
    "        res=maxc\n",
    "        while q:\n",
    "            c, x,y = heappop(q)  # q.pop()\n",
    "            if (x,y) in vis:\n",
    "                continue\n",
    "            vis.add((x,y))\n",
    "            if [x,y]==end:\n",
    "                # print((x,y,c))\n",
    "                # res=min(res,c)\n",
    "                return c\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if m>xx>=0<=yy<n:\n",
    "                    if d[matrix[x][y]]==(dx,dy):\n",
    "                        cc=c\n",
    "                    else:\n",
    "                        cc=c+1\n",
    "                    if (xx,yy) not in vis and cc<=maxc:\n",
    "                        heappush(q, (cc,xx,yy))  # q.appendleft((xx,yy,cc))\n",
    "                        # vis.add((xx,yy,cc))\n",
    "        return res\n",
    "    def conveyorBelt_my1(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        # 100*100\n",
    "        # 从start花费cost到达[i,j],记为(i,j,c) , 最大 maxc\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        maxc = abs(start[0]-end[0])+abs(start[1]-end[1])\n",
    "        q = [] # q=deque()\n",
    "        heappush(q,(0, start[0],start[1]))  # q.appendleft((start[0],start[1],0))\n",
    "        vis=set()\n",
    "        vis.add((start[0],start[1],0))\n",
    "        d={'^':(-1,0),'v':(1,0),'<':(0,-1),'>':(0,1)}\n",
    "        res=maxc\n",
    "        while q:\n",
    "            c, x,y = heappop(q)  # q.pop()\n",
    "            if [x,y]==end:\n",
    "                # print((x,y,c))\n",
    "                # res=min(res,c)\n",
    "                return c\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if m>xx>=0<=yy<n:\n",
    "                    if d[matrix[x][y]]==(dx,dy):\n",
    "                        cc=c\n",
    "                    else:\n",
    "                        cc=c+1\n",
    "                    if (xx,yy,cc) not in vis and cc<=maxc:\n",
    "                        heappush(q, (cc,xx,yy))  # q.appendleft((xx,yy,cc))\n",
    "                        vis.add((xx,yy,cc))\n",
    "        return res\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        # 100*100 my_bfs\n",
    "        # 从start花费cost到达[i,j],记为(i,j,c) , 最大 maxc\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        maxc = abs(start[0]-end[0])+abs(start[1]-end[1])\n",
    "        q=deque() # q = [] \n",
    "        q.appendleft((start[0],start[1],0)) # heappush(q,(0, start[0],start[1]))  # q.appendleft((start[0],start[1],0))\n",
    "        vis=set()\n",
    "        vis.add((start[0],start[1],0))\n",
    "        d={'^':(-1,0),'v':(1,0),'<':(0,-1),'>':(0,1)}\n",
    "        res=maxc\n",
    "        while q:\n",
    "            x,y,c = q.pop()  # ,y,c = q.pop()  # c, x,y = heappop(q)\n",
    "            if [x,y]==end:\n",
    "                # print((x,y,c))\n",
    "                res=min(res,c)\n",
    "                # return c\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if m>xx>=0<=yy<n:\n",
    "                    if d[matrix[x][y]]==(dx,dy):\n",
    "                        cc=c\n",
    "                    else:\n",
    "                        cc=c+1\n",
    "                    if (xx,yy,cc) not in vis and cc<=maxc:\n",
    "                        q.appendleft((xx,yy,cc)) # heappush(q, (cc,xx,yy)) \n",
    "                        vis.add((xx,yy,cc))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        # 图问题\n",
    "        m, n = len(matrix), len(matrix[0])  # 矩形的长宽\n",
    "        max_cost = abs(start[0]-end[0]) + abs(start[1]-end[1]) # 最大开销是每个地方都施法一次，直接走横线和竖线\n",
    "        q = deque()\n",
    "        q.appendleft((start[0], start[1], 0))  # 保存状态(x, y, cost)，表示从起点到x, y的目前最小花费为cost\n",
    "        visited = set()\n",
    "        visited.add((start[0], start[1], 0))\n",
    "        state_map = {'^': (-1, 0), 'v': (1, 0), '<': (0, -1), '>': (0, 1)}\n",
    "        results = max_cost\n",
    "        while q:\n",
    "            x, y, cost = q.pop()\n",
    "            # if (x, y) in visited:  # 如果返回的话，一定是非最小值，所以直接放弃\n",
    "            #     continue\n",
    "            # visited.add((x, y, cost))\n",
    "            if [x, y] == end:\n",
    "                # print((x, y, cost))\n",
    "                results = min(results, cost)\n",
    "                # return cost\n",
    "            for (dx, dy) in [(1,0),(-1,0),(0,1),(0,-1)]:\n",
    "                xx, yy = x+dx, y+dy\n",
    "                if 0 <= xx < m and 0 <= yy < n:\n",
    "                    if state_map[matrix[x][y]] == (dx, dy):\n",
    "                        cc = cost\n",
    "                    else:\n",
    "                        cc = cost + 1  # 如果能到则不用改，否则cost+1说明要改\n",
    "                    if (xx, yy, cc) not in visited and cc <= max_cost:  # 要保证这个值小于最大值才有意义，不过我觉得到不必\n",
    "                        q.appendleft((xx, yy, cc))\n",
    "                        visited.add((xx, yy, cc))\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt_hq(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        # 100*100\n",
    "        # 从start花费cost到达[i,j],记为(i,j,c) , 最大 maxc\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        maxc = abs(start[0]-end[0])+abs(start[1]-end[1])\n",
    "        q = [] # q=deque()\n",
    "        heappush(q,(0, start[0],start[1]))  # q.appendleft((start[0],start[1],0))\n",
    "        vis=set()\n",
    "        \n",
    "        d={'^':(-1,0),'v':(1,0),'<':(0,-1),'>':(0,1)}\n",
    "        res=maxc\n",
    "        while q:\n",
    "            c, x,y = heappop(q)  # q.pop()\n",
    "            if (x,y) in vis:\n",
    "                continue\n",
    "            vis.add((x,y))\n",
    "            if [x,y]==end:\n",
    "                # print((x,y,c))\n",
    "                # res=min(res,c)\n",
    "                return c\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if m>xx>=0<=yy<n:\n",
    "                    if d[matrix[x][y]]==(dx,dy):\n",
    "                        cc=c\n",
    "                    else:\n",
    "                        cc=c+1\n",
    "                    if (xx,yy) not in vis and cc<=maxc:\n",
    "                        heappush(q, (cc,xx,yy))  # q.appendleft((xx,yy,cc))\n",
    "                        # vis.add((xx,yy,cc))\n",
    "        return res\n",
    "    def conveyorBelt_my1(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        # 100*100\n",
    "        # 从start花费cost到达[i,j],记为(i,j,c) , 最大 maxc\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        maxc = abs(start[0]-end[0])+abs(start[1]-end[1])\n",
    "        q = [] # q=deque()\n",
    "        heappush(q,(0, start[0],start[1]))  # q.appendleft((start[0],start[1],0))\n",
    "        vis=set()\n",
    "        vis.add((start[0],start[1],0))\n",
    "        d={'^':(-1,0),'v':(1,0),'<':(0,-1),'>':(0,1)}\n",
    "        res=maxc\n",
    "        while q:\n",
    "            c, x,y = heappop(q)  # q.pop()\n",
    "            if [x,y]==end:\n",
    "                # print((x,y,c))\n",
    "                # res=min(res,c)\n",
    "                return c\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if m>xx>=0<=yy<n:\n",
    "                    if d[matrix[x][y]]==(dx,dy):\n",
    "                        cc=c\n",
    "                    else:\n",
    "                        cc=c+1\n",
    "                    if (xx,yy,cc) not in vis and cc<=maxc:\n",
    "                        heappush(q, (cc,xx,yy))  # q.appendleft((xx,yy,cc))\n",
    "                        vis.add((xx,yy,cc))\n",
    "        return res\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        # 100*100 my_bfs\n",
    "        # 从start花费cost到达[i,j],记为(i,j,c) , 最大 maxc\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        maxc = abs(start[0]-end[0])+abs(start[1]-end[1])\n",
    "        q=deque() # q = [] \n",
    "        q.appendleft((start[0],start[1],0)) # heappush(q,(0, start[0],start[1]))  # q.appendleft((start[0],start[1],0))\n",
    "        vis=set()\n",
    "        vis.add((start[0],start[1],0))\n",
    "        d={'^':(-1,0),'v':(1,0),'<':(0,-1),'>':(0,1)}\n",
    "        res=maxc\n",
    "        while q:\n",
    "            x,y,c = q.pop()  # ,y,c = q.pop()  # c, x,y = heappop(q)\n",
    "            if [x,y]==end:\n",
    "                # print((x,y,c))\n",
    "                res=min(res,c)\n",
    "                # return c\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if m>xx>=0<=yy<n:\n",
    "                    if d[matrix[x][y]]==(dx,dy):\n",
    "                        cc=c\n",
    "                    else:\n",
    "                        cc=c+1\n",
    "                    if (xx,yy,cc) not in vis and cc<=maxc:\n",
    "                        q.appendleft((xx,yy,cc)) # heappush(q, (cc,xx,yy)) \n",
    "                        vis.add((xx,yy,cc))\n",
    "        return res\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def conveyorBelt_hq(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        # 100*100\n",
    "        # 从start花费cost到达[i,j],记为(i,j,c) , 最大 maxc\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        maxc = abs(start[0]-end[0])+abs(start[1]-end[1])\n",
    "        q = [] # q=deque()\n",
    "        heappush(q,(0, start[0],start[1]))  # q.appendleft((start[0],start[1],0))\n",
    "        vis=set()\n",
    "        \n",
    "        d={'^':(-1,0),'v':(1,0),'<':(0,-1),'>':(0,1)}\n",
    "        res=maxc\n",
    "        while q:\n",
    "            c, x,y = heappop(q)  # q.pop()\n",
    "            if (x,y) in vis:\n",
    "                continue\n",
    "            vis.add((x,y))\n",
    "            if [x,y]==end:\n",
    "                # print((x,y,c))\n",
    "                # res=min(res,c)\n",
    "                return c\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if m>xx>=0<=yy<n:\n",
    "                    if d[matrix[x][y]]==(dx,dy):\n",
    "                        cc=c\n",
    "                    else:\n",
    "                        cc=c+1\n",
    "                    if (xx,yy) not in vis and cc<=maxc:\n",
    "                        heappush(q, (cc,xx,yy))  # q.appendleft((xx,yy,cc))\n",
    "                        # vis.add((xx,yy,cc))\n",
    "        return res\n",
    "    def conveyorBelt_my1(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        # 100*100\n",
    "        # 从start花费cost到达[i,j],记为(i,j,c) , 最大 maxc\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        maxc = abs(start[0]-end[0])+abs(start[1]-end[1])\n",
    "        q = [] # q=deque()\n",
    "        heappush(q,(0, start[0],start[1]))  # q.appendleft((start[0],start[1],0))\n",
    "        vis=set()\n",
    "        vis.add((start[0],start[1],0))\n",
    "        d={'^':(-1,0),'v':(1,0),'<':(0,-1),'>':(0,1)}\n",
    "        res=maxc\n",
    "        while q:\n",
    "            c, x,y = heappop(q)  # q.pop()\n",
    "            if [x,y]==end:\n",
    "                # print((x,y,c))\n",
    "                # res=min(res,c)\n",
    "                return c\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if m>xx>=0<=yy<n:\n",
    "                    if d[matrix[x][y]]==(dx,dy):\n",
    "                        cc=c\n",
    "                    else:\n",
    "                        cc=c+1\n",
    "                    if (xx,yy,cc) not in vis and cc<=maxc:\n",
    "                        heappush(q, (cc,xx,yy))  # q.appendleft((xx,yy,cc))\n",
    "                        vis.add((xx,yy,cc))\n",
    "        return res\n",
    "    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:\n",
    "        # 100*100 my_bfs\n",
    "        # 从start花费cost到达[i,j],记为(i,j,c) , 最大 maxc\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        maxc = abs(start[0]-end[0])+abs(start[1]-end[1])\n",
    "        q=deque() # q = [] \n",
    "        q.appendleft((start[0],start[1],0)) # heappush(q,(0, start[0],start[1]))  # q.appendleft((start[0],start[1],0))\n",
    "        vis=set()\n",
    "        vis.add((start[0],start[1],0))\n",
    "        d={'^':(-1,0),'v':(1,0),'<':(0,-1),'>':(0,1)}\n",
    "        res=maxc\n",
    "        while q:\n",
    "            x,y,c = q.pop()  # ,y,c = q.pop()  # c, x,y = heappop(q)\n",
    "            if [x,y]==end:\n",
    "                # print((x,y,c))\n",
    "                res=min(res,c)\n",
    "                # return c\n",
    "            di = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            for dx,dy in di:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if m>xx>=0<=yy<n:\n",
    "                    if d[matrix[x][y]]==(dx,dy):\n",
    "                        cc=c\n",
    "                    else:\n",
    "                        cc=c+1\n",
    "                    if (xx,yy,cc) not in vis and cc<=maxc:\n",
    "                        q.appendleft((xx,yy,cc)) # heappush(q, (cc,xx,yy)) \n",
    "                        vis.add((xx,yy,cc))\n",
    "        return res\n",
    "    "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
